package com.torlesse.leetcode.algorithm.common;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: torlesse-liang
 * @Date: 2022/03/06/23:07
 * @Description: 快速排序
 */
public class QuickSort {
    public static void main(String[] args) {
        quickSort(Swap.array,0,Swap.array.length - 1);
        Swap.print(Swap.array);
    }

    /**
     * 快速排序
     * 两个哨兵i,j分别从数组左端、右端进行扫描
     *
     * (a)先从右端开始扫描：哨兵j先从右端开始扫描，确保右端元素>基准值，当发现元素<基准值则对该值进行交换（当前元素赋值给哨兵i所在位置元素），此时哨兵j停止扫描
     * (b)当哨兵j停止扫描后：哨兵i从左端开始扫描，确保左端元素<基准值，当发现元素>基准值则对该值进行交换（当前元素赋值给哨兵j所在位置元素），此时哨兵i停止扫描
     *
     * 此后哨兵i，j继续从当前位置向左、向右继续扫描，继续执行以上(a)(b)操作，直到哨兵i,j相遇，然后将基准值赋值给哨兵i,j所在元素的位置（基准归位），则执行完一趟扫描。以此类推，即可完成排序。
     * @param array
     */
    public static void quickSort(int[] array,int _left,int _right){
        int left = _left;
        int right = _right;
        int temp = 0;
        if(left <= right){
            temp = array[left];
            while (left != right){
                while (left < right && array[right] >= temp){
                    right--;
                }
                array[left] = array[right];
                while (left < right && array[left] <= temp){
                    left ++;
                }
                array[right] = array[left];
            }
            //基准归位
            array[right] = temp;
            quickSort(array,_left,left - 1);
            quickSort(array,right + 1,_right);
        }
    }
}
